package william.array;


/**
 * @author ZhangShenao
 * @date 2024/4/22
 * @description <a href="https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150">...</a>
 */
public class Leetcode169_多数元素 {
    /**
     * 采用Boyer-Moore投票算法
     * 类似一种对子的思想
     * 记录候选元素candidate及其出现的次数count,初始时candidate=nums[0],count=1
     * 遍历数组,针对每一个元素进行判断:
     * - 如果count=0,说明之前不相等的元素已经抵消,则将当前元素设置为candidate,并将count设置为1
     * - 如果count!=0,则判断当前元素与candidate是否相等。如果不相等,则进行抵消操作,将count-1;否则将count+1
     * 最后返回candidate即为众数元素
     * <p>
     * 时间复杂度O(N) 仅遍历数组一次
     * 空间复杂度O(1)
     */
    public int majorityElement(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 1) {
            throw new IllegalArgumentException("majority element not exists!");
        }

        //记录候选元素candidate及其出现的次数count,初始时candidate=nums[0],count=1
        int candidate = nums[0];
        int count = 1;

        //遍历数组,针对每一个元素进行判断
        for (int i = 1; i < nums.length; i++) {
            int n = nums[i];
            if (count == 0) {    //count=0,说明之前不相等的元素已经抵消,则将当前元素设置为candidate,并将count设置为1
                candidate = n;
                count++;
                continue;
            }

            if (candidate == n) {    //当前元素与候选元素相等,将count+1
                ++count;
            } else { //当前元素与候选元素不相等,则进行抵消操作,将count-1
                --count;
            }
        }

        //最终返回幸存的candidate,即为众数元素
        return candidate;
    }
}
